package top.guoziyang.mydb.backend.im;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import top.guoziyang.mydb.backend.common.SubArray;
import top.guoziyang.mydb.backend.dm.DataManager;
import top.guoziyang.mydb.backend.dm.dataItem.DataItem;
import top.guoziyang.mydb.backend.im.Node.InsertAndSplitRes;
import top.guoziyang.mydb.backend.im.Node.LeafSearchRangeRes;
import top.guoziyang.mydb.backend.im.Node.SearchNextRes;
import top.guoziyang.mydb.backend.tm.TransactionManagerImpl;
import top.guoziyang.mydb.backend.utils.Parser;

public class BPlusTree {
    DataManager dm;
    long bootUid;
    DataItem bootDataItem; //在 bootDataItem 中存储的正是根节点的 UID
    Lock bootLock;


    /**
     * 初始化一个新的 B+ 树，并将其根节点存储在DM中
     */
    public static long create(DataManager dm) throws Exception {
        byte[] rawRoot = Node.newNilRootRaw();
        long rootUid = dm.insert(TransactionManagerImpl.SUPER_XID, rawRoot);  //返回根节点在dm中的UID，通过 UID，可以在后续操作中检索和引用该根节点
        return dm.insert(TransactionManagerImpl.SUPER_XID, Parser.long2Byte(rootUid)); // 返回值是新的 UID，表示存储根节点 UID 的数据项的标识符
    }

    /**
     * 根据 bootUid 从DM中加载一个已存在的 B+树实例。
     */
    public static BPlusTree load(long bootUid, DataManager dm) throws Exception {
        DataItem bootDataItem = dm.read(bootUid);
        assert bootDataItem != null;
        BPlusTree t = new BPlusTree();
        t.bootUid = bootUid;
        t.dm = dm;
        t.bootDataItem = bootDataItem;
        t.bootLock = new ReentrantLock();
        return t;
    }

    /**
     * 获取当前 B+树的根节点 UID
     */
    private long rootUid() {
        bootLock.lock();
        try {
            SubArray sa = bootDataItem.data();
            return Parser.parseLong(Arrays.copyOfRange(sa.raw, sa.start, sa.start+8));
        } finally {
            bootLock.unlock();
        }
    }

    /**
     * 更新 B+树的根节点 的UID（例如，在根节点分裂时需要更新）
     */
    private void updateRootUid(long left, long right, long rightKey) throws Exception {
        bootLock.lock();
        try {
            byte[] rootRaw = Node.newRootRaw(left, right, rightKey); // 创建一个新的根节点的字节数组
            long newRootUid = dm.insert(TransactionManagerImpl.SUPER_XID, rootRaw); //将新根节点的数据插入到数据管理器 dm 中，返回其 UID
            bootDataItem.before(); //开启事务，保存旧数据（用于支持回滚）
            SubArray diRaw = bootDataItem.data(); //从 diRaw.raw 中提取原始数据
            System.arraycopy(Parser.long2Byte(newRootUid), 0, diRaw.raw, diRaw.start, 8); //将新根的UID的字节表示覆盖diRaw的UID
            bootDataItem.after(TransactionManagerImpl.SUPER_XID); //为SUPER_XID生成一条update日志,并记录当前数据项( this) 的内容
        } finally {
            bootLock.unlock();
        }
    }

    /**
     * 递归地搜索包含指定键值 key 的 叶子节点 UID
     */
    private long searchLeaf(long nodeUid, long key) throws Exception {
        Node node = Node.loadNode(this, nodeUid); // 加载当前节点
        boolean isLeaf = node.isLeaf(); // 判断是否为叶子节点
        node.release(); // 释放节点资源

        if(isLeaf) { // 如果是叶子节点，返回当前节点 UID
            return nodeUid;
        } else {   // 否则递归搜索下一级
            long next = searchNext(nodeUid, key);  // 找到下一个子节点
            return searchLeaf(next, key); // 递归调用
        }
    }

    /**
     * 在非叶子节点中，根据 key 找到对应的子节点 UID
     */
    private long searchNext(long nodeUid, long key) throws Exception {
        while(true) {
            Node node = Node.loadNode(this, nodeUid);
            SearchNextRes res = node.searchNext(key);
            node.release();
            if(res.uid != 0) return res.uid;
            nodeUid = res.siblingUid;
        }
    }

    /**
     * 将单个键值的查询视为范围查询 [key, key] 的特殊情况
     */
    public List<Long> search(long key) throws Exception {
        return searchRange(key, key);
    }

    /**
     * 查询键值范围 [leftKey, rightKey] 内的所有数据 UID
     */
    public List<Long> searchRange(long leftKey, long rightKey) throws Exception {
        long rootUid = rootUid();   // 获取根节点 UID
        long leafUid = searchLeaf(rootUid, leftKey); // 找到包含 leftKey 的叶子节点
        List<Long> uids = new ArrayList<>(); // 存储查询结果
        while(true) {
            Node leaf = Node.loadNode(this, leafUid); // 加载当前叶子节点
            LeafSearchRangeRes res = leaf.leafSearchRange(leftKey, rightKey); // 查询范围
            leaf.release();
            uids.addAll(res.uids); // 添加当前节点的结果
            if(res.siblingUid == 0) {  // 如果没有兄弟节点，退出循环
                break;
            } else {  // 否则继续查询下一个兄弟节点
                leafUid = res.siblingUid;
            }
        }
        return uids;
    }

    /**
     * 插入新的键值对 (key, uid)
     */
    public void insert(long key, long uid) throws Exception {
        long rootUid = rootUid();  // 获取根节点 UID
        InsertRes res = insert(rootUid, uid, key);  // 插入数据，返回插入结果
        assert res != null;
        if(res.newNode != 0) {  // 如果插入引发了根节点分裂
            updateRootUid(rootUid, res.newNode, res.newKey); // 更新根节点 UID
        }
    }

    class InsertRes {
        long newNode; //如果节点发生分裂，新分裂节点的 UID
        long newKey; //如果节点发生分裂，新分裂节点的第一个键值（用于更新父节点）
    }

    /**
     * 在指定节点中递归插入 (key, uid)，并处理节点分裂及其向上传播
     * 分别处理叶子节点和非叶子节点的插入逻辑
     */
    private InsertRes insert(long nodeUid, long uid, long key) throws Exception {
        Node node = Node.loadNode(this, nodeUid); // 加载当前节点
        boolean isLeaf = node.isLeaf(); // 判断是否为叶子节点
        node.release(); // 释放节点资源

        InsertRes res = null;
        if(isLeaf) { // 如果是叶子节点
            res = insertAndSplit(nodeUid, uid, key); // 在叶子节点插入数据并处理分裂
        } else {  // 如果是非叶子节点
            long next = searchNext(nodeUid, key);  // 找到目标子节点
            InsertRes ir = insert(next, uid, key); // 递归插入到子节点
            if(ir.newNode != 0) {  // 如果子节点发生分裂
                res = insertAndSplit(nodeUid, ir.newNode, ir.newKey); // 在当前节点插入新分裂的节点信息
            } else {
                res = new InsertRes(); // 如果没有分裂，返回空结果
            }
        }
        return res;
    }

    /**
     * 在指定节点插入键值对 (key, uid)
     * 如果插入导致节点分裂，返回分裂结果
     */
    private InsertRes insertAndSplit(long nodeUid, long uid, long key) throws Exception {
        while(true) {
            Node node = Node.loadNode(this, nodeUid);
            InsertAndSplitRes iasr = node.insertAndSplit(uid, key);
            node.release();
            if(iasr.siblingUid != 0) { // 如果兄弟节点不为空,说明当前节点已满，跳转到兄弟节点继续插入
                nodeUid = iasr.siblingUid;
            } else {  // 如果插入完成，返回分裂结果
                InsertRes res = new InsertRes();
                res.newNode = iasr.newSon; // 新分裂节点的 UID
                res.newKey = iasr.newKey; // 新分裂节点的第一个键值
                return res;
            }
        }
    }

    public void close() {
        bootDataItem.release();
    }
}
